//nowcoderJZ36 二叉搜索树与双向链表

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution{
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
	{
		TreeNode* prev = nullptr;
        convertToList(pRootOfTree, prev);

		TreeNode* head = pRootOfTree;
		while(head && head->left) head = head->left;
		
		return head;
    }

	void convertToList(TreeNode* cur, TreeNode*& prev)
	{
		if (cur == nullptr) return;

		//在中序遍历的过程中完成将二叉搜索树转变为双向链表
		convertToList(cur->left, prev);

		//递归是顾头不顾尾的 只找得到当前节点和前一个节点 但不知道后一个节点
		//所以只有prev和cur指针 没有next指针
		//但是在再进行一次递归之后 prev就会变成cur cur就会变成next 这样就能找到下一个节点了
		cur->left = prev;
		//在第一次进行连接的时候 prev为nullptr
		if (prev) prev->right = cur;

		//在递归的过程prev在不断更新 但是这个prev只是局部变量 
		//最多“继承”给下一层递归 但是上层递归是看不见的 所以prev传参时要传引用
		prev = cur;

		convertToList(cur->right, prev);
	}
};